package com.cuz.hot100;

import java.util.Arrays;


public class Q4findMedianSortedArrays {
    public static void main(String[] args) {
        int[] arr1 = {1, 2, 7, 8, 9};
        int[] arr2 = {2, 3, 4, 5, 10};
        System.out.println(findMedianSortedArrays(arr1, arr2));
        System.out.println(Solution.findMedianSortedArrays(arr1, arr2));
        int[] arr3 = new int[arr1.length + arr2.length];
        int count = 0;
        while (count < arr3.length) {
            if (count < arr1.length) {
                arr3[count] = arr1[count];
            } else {
                arr3[count] = arr2[count - arr1.length];
            }
            count++;
        }
        Arrays.sort(arr3);
        if (arr3.length % 2 == 0) {
            int midIndex1 = arr3.length / 2;
            int x = arr3[midIndex1] + arr3[midIndex1 - 1];
            System.out.println(x / 2.0);
        } else {
            System.out.println(arr3[arr3.length / 2]);
        }
    }


    public static double findMedianSortedArrays(int[] arr1, int[] arr2) {
        int len1 = arr1.length;
        int len2 = arr2.length;
        if (len1 > len2) {
            return findMedianSortedArrays(arr2, arr1);
        }
        int left = -1;
        int right = len1 + 1;
        int mid1 = 0;
        int mid2 = 0;
        int i = 0;
        int j = 0;
        while (left <= right) {
            i = (right + left) / 2;
            j = (len1 + len2 + 1) / 2 - i;
            int arr1LeftMax = Integer.MIN_VALUE;
            if (i != 0) {
                arr1LeftMax = arr1[i - 1];
            }
            int arr1RightMin = Integer.MAX_VALUE;
            if (i < arr1.length) {
                arr1RightMin = arr1[i];
            }
            int arr2LeftMax = Integer.MIN_VALUE;
            if (j != 0) {
                arr2LeftMax = arr2[j - 1];
            }
            int arr2RightMin = Integer.MAX_VALUE;
            if (j < arr2.length) {
                arr2RightMin = arr2[j];
            }
            if (arr1LeftMax <= arr2RightMin) {
                left = i + 1;
                mid1 = Math.max(arr1LeftMax, arr2LeftMax);
                mid2 = Math.max(arr1RightMin, arr2RightMin);
            } else {
                right = i - 1;
            }
        }
        if ((len1 + len2) % 2 == 0) {
            return (mid1 + mid2) / 2.0;
        }
        return mid1;
    }


    static class Solution {
        public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if (nums1.length > nums2.length) {
                return findMedianSortedArrays(nums2, nums1);
            }
            int len1 = nums1.length;
            int len2 = nums2.length;
            int left = 0, right = len1;
            // median1：前一部分的最大值
            // median2：后一部分的最小值
            int median1 = 0, median2 = 0;
            while (left <= right) {
                // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
                // 后一部分包含 nums1[i .. len1-1] 和 nums2[j .. len2-1]
                int i = (left + right) / 2;
                int j = (len1 + len2 + 1) / 2 - i;
                // arr1LeftMax, arr1RightMin, arr2LeftMax, arr1RightMin 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
                int arr1LeftMax = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
                int arr1RightMin = (i == len1 ? Integer.MAX_VALUE : nums1[i]);
                int arr2LeftMax = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
                int arr2RightMin = (j == len2 ? Integer.MAX_VALUE : nums2[j]);

                if (arr1LeftMax <= arr2RightMin) {
                    median1 = Math.max(arr1LeftMax, arr2LeftMax);
                    median2 = Math.min(arr1RightMin, arr2RightMin);
                    left = i + 1;
                } else {
                    right = i - 1;
                }
            }
            return (len1 + len2) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
        }
    }
}
